using System;
using System.Collections.Generic;
using System.Data.Linq;

using adt.assoc.DictionaryExtentions;



namespace adt.tree.search
{
	public interface TreePattern<T>
	{
		MatchObject<T> Match(Tree<T> tree);
	}
	
	public class MatchObject<T>
	{
		public Tree<T> At;
		public IDictionary<T, Tree<T>> Groups;
		
		public override string ToString()
		{
			return string.Format("Matched {0} ({1})", At, Groups.Repr());
		}
	}

	public struct WildcardPredicates<T>
	{
		public Func<T, bool> IsWildNode;
		public Func<T, bool> IsWildSubtree;
		public Func<T, bool> IsWildSubtrees;
	}
		
	
	/**
	 * Matches the upper part of the tree against a constant template.
	 * The template may contain "wildcards", which can match against any value 
	 * or any subtree; When they are encountered, the MatchObject's Groups 
	 * dictionary is filled with corresponding data.
	 */
	public class TreeTopPattern<T> : TreePattern<T> where T : IComparable
	{
		private Tree<T> template;
		private WildcardPredicates<T> wildcards;
		
		public TreeTopPattern(Tree<T> template) : this(template, DEFAULT_WILDCARDS) { }
		
		public TreeTopPattern(Tree<T> template, WildcardPredicates<T> wildcards)
		{
			this.template = template;
			this.wildcards = wildcards;
		}
		
		public MatchObject<T> Match(Tree<T> text)
		{
			return Match(text, template);
		}
			
		public MatchObject<T> Match(Tree<T> text, Tree<T> template)
		{
			// Check for subtree wildcard
			if (wildcards.IsWildSubtree(template.Root)) {
				return new MatchObject<T>()
				{ At = text, 
				  Groups = new Dictionary<T, Tree<T>>() { { template.Root, text} } };
			}
			
			// Check for node wildcard
			bool wild_node = wildcards.IsWildNode(template.Root);
			
			if ((wild_node || text.Root.Equals(template.Root)) && 
			    text.Subtrees.Count == template.Subtrees.Count) {
				// initial groups dictionary
				var g = new Dictionary<T, Tree<T>>();
				if (wild_node) g[template.Root] = text;
				// check subtrees
				for (int i = 0; i < text.Subtrees.Count; ++i) {
					var smo = Match(text.Subtrees[i], template.Subtrees[i]);
					if (smo == null) return null;
					g.Update(smo.Groups);
				}
				return new MatchObject<T>() { At = text, Groups = g };
			}
			else
				return null;
		}
		
		public static WildcardPredicates<T> DEFAULT_WILDCARDS = new WildcardPredicates<T>() 
		 { IsWildNode = (x) => x.Equals("?"), IsWildSubtree = (x) => x.Equals("*"),
			IsWildSubtrees = (x) => x.Equals("...") };
	}
}

